package lsl.leetCode.year2023.test0124;

/**
 * 求最大子数组的和
 */
public class test53 {
    public static void main(String[] args) {
        int[] nums = {1,-2, -2, 3, 3,-1,4};
        System.out.println(maxSubArray(nums));
    }
    //1.使用动态规划
    public static int maxSubArray(int[] nums) {
        int preSum=0;
        int maxAns = nums[0];
        for (int i = 0; i <nums.length ; i++) {
            //1.1数组中前i个数的和
            preSum+=nums[i];
            //1.2如果数组中前i-1个数的和加上当前数i的和小于当前数i的值
            //1.3说明前i-1个数的和为负数，那么从第i个数开始重新计算
            if(preSum<nums[i]){
                preSum=nums[i];
            }
            maxAns=Math.max(maxAns,preSum);
        }
        return maxAns;
    }
}
